1. Finite automata, Regular languages, Regular grammars:
Deterministic vs. nondeterministic, one-way vs. two-way finite automata, minimization,
pumping lemma for regular sets, closure properties.
2. Pushdown automata, Context-free languages, Context-free grammars:
Deterministic vs. nondeterministic, one-way vs. two-way PDAs, reversal bounded PDAs,
linear grammars, counter machines, pumping lemma for CFLs, Chomsky normal form,
Greibach normal form, closure properties.
3. Linear bounded automata, Context-sensitive languages, Context-sensitive grammars.
4. Turing machines, Recursively enumerable sets, Type 0 grammars:
Variants of Turing machines, halting problem, undecidability, Post correspondence
problem, valid and invalid computations of TMs.
5. Basic recursive function theory
6. Basic complexity theory:
Various resource bounded complexity classes, including NLOGSPACE, P, NP,
PSPACE, EXPTIME, and many more. reducibility, completeness.
7. Advanced topics in complexity theory:
Approximation algorithms, probabilistic complexity, parallel complexity, Alternation,
interactive proof systems, oracle computations.